package 中等.分类讨论;

/**
 * 给你一个 m x n 的二进制矩阵 grid 。
 * 如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
 * 你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
 * 请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。
 *
 * @ https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/description/?envType=daily-question&envId=2024-11-16
 * @date 2024/11/16
 */
public class 最少翻转次数使二进制矩阵回文II_3240 {

    public static void main(String[] args) {

        最少翻转次数使二进制矩阵回文II_3240 impl = new 最少翻转次数使二进制矩阵回文II_3240();
        System.out.println(impl.minFlips(new int[][]{
                {0, 1, 1, 1},
                {1, 0, 1, 1}}));

    }

    /**
     * 分类讨论
     * 从特殊到一般思考
     * 1，2*2 的矩阵，要么全是 4 个 1 ，要么全是 4 个 0
     * 2，4*4 的矩阵，发现回文对应的 4 个位置要么都是 1，要么都是 0 ，1 的数目是 4 的倍数
     * 1 0 0 1
     * 0 0 0 0
     * 0 0 0 0
     * 1 0 0 1
     * 3，5*5 的矩阵，中间的 [2,2] 必须是0，不然不能满足4倍数的条件
     * 1 0 - 0 1
     * 0 0 - 0 0
     * - - - - -
     * 0 0 - 0 0
     * 1 0 - 0 1
     * 统计中间部分对应回文位置不同数字的个数 diff 和 都是 1 的 1 的个数 cnt1
     * 分类讨论
     * 如果 cnt1 % 4 == 0 ，那么 diff 都变 0，是 4 的倍数
     * 如果 cnt1 % 4 == 2 ，
     * *    diff > 0 可以把 diff 的其中一对变成 1
     * *    diff = 0 需要把 cnt1 中 2 个 1 变成 0
     */
    public int minFlips(int[][] grid) {
        int ans = 0;
        int columns = grid[0].length, rows = grid.length;

        for (int i = 0; i < rows / 2; i++) {
            for (int j = 0; j < columns / 2; j++) {
                int[] cnt = new int[2];
                cnt[grid[i][j]]++;
                cnt[grid[rows - i - 1][j]]++;
                cnt[grid[i][columns - j - 1]]++;
                cnt[grid[rows - i - 1][columns - j - 1]]++;
                ans += Math.min(cnt[0], cnt[1]);
            }
        }
        int cnt1 = 0, diff = 0;
        if (rows % 2 == 1) {
            int i = rows / 2;
            for (int j = 0; j < columns / 2; j++) {
                if (grid[i][j] == 1 && grid[i][columns - j - 1] == 1) {
                    cnt1 += 2;
                } else if (grid[i][j] + grid[i][columns - j - 1] == 1) {
                    diff++;
                }
            }
        }
        if (columns % 2 == 1) {
            int j = columns / 2;
            for (int i = 0; i < rows / 2; i++) {
                if (grid[i][j] == 1 && grid[rows - i - 1][j] == 1) {
                    cnt1 += 2;
                } else if (grid[i][j] + grid[rows - i - 1][j] == 1) {
                    diff++;
                }
            }
        }

        if (cnt1 % 4 == 2 && diff == 0) {
            ans += 2;
        } else {
            ans += diff;
        }
        if (rows % 2 == 1 && columns % 2 == 1 && grid[rows / 2][columns / 2] == 1) {
            ans++;
        }
        return ans;
    }

}
